package com.mdnote.practice.generic_recursion;

/**
 * @author Rhythm-2019
 * @date 2020/9/14
 * @description 爬楼梯问题
 */
public class LeetCode70 {

    public static void main(String[] args) {
        LeetCode70 leetCode70 = new LeetCode70();
        // 传入希望到达的部署
        int res = leetCode70.climbStairRecursion(8);
        System.out.println(res);
    }

    /**
     * 动态规划
     * @param n 希望到达的步数
     * @return 返回可能性
     */
    public int climbStairDP(int n) {

        // 比如n = 1 可能性为 1
        // n = 2， 可以2次1步，或者1次2步
        // n = 3， 可以3次1步，1次两步1次一步，1次一步1次两步
        // n = 4， 一共5种 f(2) + f(3)

        // 可以使用动态规划维护一个一维数组
        int[] res = new int[n + 1];

        // 设置初始值值
        res[0] = 1;
        res[1] = 1;

        for (int i = 2; i < res.length; i++) {
            res[i] = res[i - 1] + res[i - 2];
        }

        return res[res.length - 1];
    }

    /**
     * 动态规划
     * @param n 希望到达的步数
     * @return 返回可能性
     */
    public int climbStairDPPlus(int n) {

        // 我们可以使用三个变量来代替
        int p = 0, q = 0, r = 1;

        // 计算f(i)
        for (int i = 1; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }

        return r;
    }

    /**
     * 简单递归
     * @param n 楼梯
     * @return 可能性
     */
    public int climbStairRecursion(int n) {
        // Terminator
        if (n <= 1) {
            return 1;
        }
        // drill down
        return climbStairRecursion(n - 1) + climbStairRecursion(n - 2);
    }
}
